Magic I

Ancient magicians kept their secrets well. Some elder citizens, who saw the action of witchcraft, told us about a magic cipher hidden somewhere in our reality. If you want to reveal the secret, you must dive into the world of illusions. Are you ready?

Download: aero2020_magic.zip

Recon

We're given a zip file that contains a Python script and a text file containing the output of a run of the script.

Looking at the script, we see that it implements some form of stream cipher, and it outputs the encrypted flag as well as a transformed version of the key used for encryption.

The approach we're going with is to see if we can recreate the keystream in some way from the transformed version, then use that to decrypt the flag.

To that end, we need to understand how the cipher operates and whether there are assumptions we can make to reduce the keyspace.

Cipher

class Cipher(object):
    def __init__(self, key: int, canary: int):
        self._key = key
        self._canary = canary
        return

    @property
    def canary(self) -> int:
        return self._canary

    def encrypt(self, message: bytes) -> bytes:
        plaintext = int.from_bytes(message, 'big')
        assert self._key.bit_length() >= plaintext.bit_length()

        ciphertext = self._key ^ plaintext
        length = (ciphertext.bit_length() + 7) // 8
        return ciphertext.to_bytes(length, 'big')

    def decrypt(self, message: bytes) -> bytes:
        raise NotImplementedError

    @classmethod
    def create(cls, source: np.ndarray) -> 'Cipher':
        assert len(set(source.shape)) == 1
        line = source.reshape(-1)

        assert len(line) == len(set(line) & set(range(len(line))))
        keys = set(map(sum, chain.from_iterable((*s, np.diag(s)) for s in [source, source.T])))

        assert len(keys) == 1
        key = int(keys.pop())
        return cls(key, key % len(line))

def main():
    from secret import SECRET, FLAG
    cipher = Cipher.create(SECRET)

    print(cipher.encrypt(FLAG).hex())
    print(cipher.canary)

The cipher class, shown above, seems rather straightforward. The encrypt method implements a simple XOR operation on integers, where the key is longer than the message so it's not reused, so that doesn't immediately lead us to a solution.

Going over the rest of the class, we notice that the create method is littered with assertions about the key material.

Let's go over them one by one:

assert len(set(source.shape)) == 1: according to the numpy docs, the array shape is basically its dimensions. So an array that contains 3 lists, each of which has 4 elements has the shape (3, 4), i.e. a 3x4 matrix. This assertion ensures that the dimensions of the array are all the same value, so it could be a 1-d array, or a square matrix, or a cube and so on through higher dimensions.
line = source.reshape(-1) and assert len(line) == len(set(line) & set(range(len(line)))): according to the same numpy document, reshaping an array with -1 would create a "flattened" 1-d array of all the entries of the array. We also see an assertion that asserts that the length of the resulting 1-d array is the same as the length of the set of the intersection of its unique elements and the natural numbers in [0, array_length). The only way this is satisfied is if:
1. All the elements in the array are unique, i.e. there are no repeated entries.
2. All the elements in the array are exactly the elements in [0, array_length). These two conditions are only satisfied if the 1-d array is a permutation of [0, array_length).
keys = set(map(sum, chain.from_iterable((*s, np.diag(s)) for s in [source, source.T]))): here we're generating a set of keys from the source input. So far, we don't know how it looks like, except for the fact that all its dimensions are the same value. However, np.diag would only work with a 1-d or a 2-d array. Additionally, since its transpose is also used as source.T, we could assume that it's a square matrix.
assert len(keys) == 1: the set of keys must have length 1, which means that for both the initial matrix and its transposition, every entry must sum up to the same value, even their diagonals must sum up to the same value.

All these conditions combined, and given that the name of the challenge is "magic", this leads us to presume that the key material should be a Magic square. Magic squares are matrices of numbers that where every row and column sum up to the same number. One property of "normal" magic squares is that the summation value, called the magic constant, relies only on n, the order of the square.

The formula to determine the magic constant of a square of order n with elements $[1, n^2]$ is given by

$$M = n(n^2+1)/2$$

Since the square we're looking for fits as a 1-d array in the range $[0, n^2-1)$, we have to tweak the formula a bit:

$$ M = n(n^2 - 1)/2 $$

We're still missing the exact value of $n$. However, we have the canary value, which is defined as key % len(line). This boils down to simply $M \mod n^2$, let's write it out in full, where $C$ is the canary value:

$$ \begin{align} C &\equiv M &\mod n^2 \\ &\equiv n(n^2 - 1)/2 &\mod n^2\\ &\equiv n(-1)/2 &\mod n^2\\ &\equiv -n/2 &\mod n^2\\ &\equiv (n^2 - n)/2 &\mod n^2 \\ &\leftrightarrow \\ 2C &\equiv n^2 - n &\mod n^2 \end{align} $$

The value of $2C$ that we ended up with is actually less than $n^2$, which means that $2C = n^2 - n$. We can use this to build a quadratic equation which we can solve for $n$:

$$ n^2 - n - 2C = 0 $$

Using the positive root of the equation as the value for $n$, we can calculate the key and decrypt the flag.

Solution

import numpy as np
from gmpy2 import isqrt

c = 5405053190768240950975482839552589374748349681382030872360550121041249100085609471
b = -1
a = 1
d = b**2 - (4 * a * -2 * c)
ns = [(-b + isqrt(d)) // (2*a), (-b - isqrt(d)) // (2*a)]
n = int(max(ns))

print('N = ' + str(n))

key = (n*n*n - n) // 2
print('Key = ' + str(key))
flag = bytes.fromhex('d9a103a6006bfba17074ef571011d8eededdf851b355' +
                     'bdc4795616744066433695b9e9201f6deff7577c03ba' +
                     '690d4d517bdaae')

flag = int.from_bytes(flag, 'big')
plaintext = flag ^ key

print(plaintext)
length = (plaintext.bit_length() + 7) // 8

print(plaintext.to_bytes(length, 'big'))

Flag

$ python code.py

N = 103971661434914474977947909929808181577819
Key = 5619723603882597484119921611752831404578
      3507573054404490346638369620037700724023
      2937465352098303479813588180518349115533
      2205999450868019111308069788178321631876
      6784614025527401228818102831154360286138
      8968346504555978579832984534282

Aero{m4g1c_squ4r3_1s_just_4n_4nc13nt_puzzl3}